package interpreter;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;

import nfa_generator.NFAGenerator;
import nfa_generator.NFAGraph;
import table_walker.CompleteToken;
import table_walker.TableWalker;
import DFA.DFA;
import DFA.DFAException;
import ast_generator.ASTTree;
import ast_generator.TreeGenerator;


public class Interpreter {
	private List<List<String>> input;
	private Map<String, Variable> varMap;
	private List<String> operations = Arrays.asList("find", "#", "replace", "recursivereplace", "maxfreqstring", "=", "print");
	private List<String> binops = Arrays.asList("diff", "union", "inters");
	
	//Constructor, empty
	public Interpreter() {
		this.setInput(new ArrayList<List<String>>());
		this.setVarMap(new HashMap<String, Variable>());
	}
	
	//Constructor, with input
	public Interpreter(List<List<String>> input) {
		this.setInput(input);
		this.setVarMap(new HashMap<String, Variable>());
	}
	
	//
	public void interperate () throws Exception {
		if(input != null && input.size() > 0) {
			for(List<String> statement : input) {
				interperate(statement);
			}
		}
	}
	
	public void interperate(List<String> statement) throws Exception {
		if(operations.contains(statement.get(0))) {
			//Replace call
			if(statement.get(0).compareTo("replace") == 0) {
				replace(statement.get(1), statement.get(2), statement.get(3), statement.get(4));
			}
			//Recursive replace call
			else if(statement.get(0).compareTo("recursivereplace") == 0) {
				recursiveReplace(statement.get(1), statement.get(2), statement.get(3), statement.get(4));
			}
			//Print call
			else if(statement.get(0).compareTo("print") == 0) {
				print(statement.subList(1, statement.size()));
			}
		}
		//Assignment of existing variable
		else if(varMap.keySet().contains(statement.get(0))) {
			//ID =...
			if(statement.get(1).compareTo("=") == 0) {
				//ID = ID
				if(varMap.keySet().contains(statement.get(2))) {
					varMap.get(statement.get(0)).setValueStringMatchList(varMap.get(statement.get(2)).getValueStringMatchList());
				}
				//ID = expr...
				else {
					List<List<String>> list = evaluateExpressions(statement.subList(2, statement.size()));
					varMap.get(statement.get(0)).setValueStringMatchList(list);
				}
			}
			//ID = #...
			else if(statement.get(1).compareTo("#") == 0) {
				//ID = #ID
				if(varMap.keySet().contains(statement.get(2))) {
					varMap.get(statement.get(0)).setValueInt(varMap.get(statement.get(2)).getValueStringMatchList().size());
				}
				//ID = #expr...
				else {
					List<List<String>> list = evaluateExpressions(statement.subList(2, statement.size()));
					varMap.get(statement.get(0)).setValueInt(list.size());
				}
			}
			//ID = maxfreqstring(ID)
			else if(statement.get(1).compareTo("maxfreqstring") == 0) {
				varMap.get(statement.get(0)).setValueStringMatchList(Arrays.asList(maxFreqString(statement.get(2))));
			}
		}
		//new ID =...
		else {
			Variable temp = new Variable(statement.get(0));
			//new ID = ID
			if(statement.get(1).compareTo("=") == 0) {
				//new ID = ID
				if(varMap.keySet().contains(statement.get(2))) {
					temp.setValue(varMap.get(statement.get(2)).getValue());
					varMap.put(statement.get(0), temp);
				}
				//new ID = expr...
				else {
					List<List<String>> list = evaluateExpressions(statement.subList(2, statement.size()));
					temp.setValueStringMatchList(list);
					varMap.put(statement.get(0), temp);
				}
			}
			//new ID = #...
			else if(statement.get(1).compareTo("#") == 0) {
				//new ID = #ID
				if(varMap.keySet().contains(statement.get(2))) {
					temp.setValueInt(varMap.get(statement.get(2)).getValueStringMatchList().size());
					varMap.put(statement.get(0), temp);
				}
				//new ID = #expr...
				else {
					List<List<String>> list = evaluateExpressions(statement.subList(2, statement.size()));
					temp.setValueInt(list.size());
					varMap.put(statement.get(0), temp);
				}
			}
			//new ID = maxfreqstring(ID)
			else if(statement.get(1).compareTo("maxfreqstring") == 0) {
				temp.setValueStringMatchList(Arrays.asList(maxFreqString(statement.get(2))));
				varMap.put(statement.get(0), temp);
			}
		}
	}
	
	/**
	 * Takes in a String list, a list of expressions tokens, and evaluates it.
	 * 
	 * @param expressions
	 * @return
	 * @throws DFAException 
	 */
	public List<List<String>> evaluateExpressions(List<String> expressions) throws DFAException {
		//Divide up continuous list of expressions into list of contained expressions
		//i.e. {{find, regex, filename},{union},{ID}}
		int i = 0;
		List<List<String>> expressionSets = new ArrayList<List<String>>();
		while(i < expressions.size()) {
			if(expressions.get(i).compareTo("find") == 0) {
				expressionSets.add(expressions.subList(i, i+3));
				i += 3;
			}
			else if(binops.contains(expressions.get(i))) {
				expressionSets.add(expressions.subList(i, i+1));
				i++;
			}
			else if(varMap.keySet().contains(expressions.get(i))) {
				expressionSets.add(expressions.subList(i, i+1));
				i++;
			}
		}
		
		//Get values of expressions
		//find or ID - > List<List<String>>
		//ID -> Int
		//bin-op -> String
		//Evaluate finds, get string match list from variables...
		List<List<List<String>>> resolvedSets = new ArrayList<List<List<String>>>();
		i=0;
		while(i < expressionSets.size()) {
			if(!binops.contains(expressionSets.get(i).get(0))) {
				if(expressionSets.get(i).get(0).compareTo("find") == 0) {
					resolvedSets.add(find(expressionSets.get(i).get(1),expressionSets.get(i).get(2)));
				}
				else if(varMap.keySet().contains(expressionSets.get(i).get(0))) {
					resolvedSets.add(varMap.get(expressionSets.get(i).get(0)).getValueStringMatchList());
				}
			}
			if(binops.contains(expressionSets.get(i).get(0))) {
				resolvedSets.add(Arrays.asList(expressionSets.get(i)));
			}
			i++;
		}
		
		//Evaluate the expressions
		i=0;
		List<List<String>> result = null;
		while(i < resolvedSets.size()) {
			if(binops.contains(resolvedSets.get(i).get(0).get(0)) || (i+1 < resolvedSets.size() && binops.contains(resolvedSets.get(i+1).get(0).get(0)))) {
				if(resolvedSets.get(i).get(0).get(0).compareTo("diff") == 0) {
					result = difference((List<List<String>>) resolvedSets.get(i-1), (List<List<String>>) resolvedSets.get(i+1));
					resolvedSets.set(i+1, result);
				}
				else if(resolvedSets.get(i).get(0).get(0).compareTo("inters") == 0) {
					result = intersection((List<List<String>>) resolvedSets.get(i-1), (List<List<String>>) resolvedSets.get(i+1));
					resolvedSets.set(i+1, result);
				}
				else if(resolvedSets.get(i).get(0).get(0).compareTo("union") == 0) {
					result = union((List<List<String>>) resolvedSets.get(i-1), (List<List<String>>) resolvedSets.get(i+1));
					resolvedSets.set(i+1, result);
				}
			}
			i++;
		}
		if(result == null) {
			return (resolvedSets.get(0));
		}
		
		return result;
	}
	
	/**
	 * Takes in an ID, String name of a Variable, and returns the most
	 * frequently occurring String in the StringMatchList of the Variable.
	 * Strings are considered as a List<String> = {String, Index, Filename}
	 * 
	 * Map uses whole List<String> as key, may change to count just String part and
	 * and handle appropriately.
	 * 
	 * @param id - String name of Variable
	 * @return - String<List> object representing the most frequently occurring String
	 */
	public List<String> maxFreqString(String id) {
		List<List<String>> varStringList = (List<List<String>>) varMap.get(id).getValue();
		HashMap<String, Integer> stringMap = new HashMap<String, Integer>();
		
		if(varStringList == null) return null;
		
		for(List<String> sl : varStringList) {
			stringMap.put(sl.get(0), 1);
			int i = 1;
			while(i < sl.size()) {
				if(sl.get(i).compareTo("<") == 0){
					i += 1;
				}
				else if (sl.get(i).compareTo(">") == 0) {
					i++;
				}
				else {
					stringMap.put(sl.get(0), stringMap.get(sl.get(0)) + 1);
					i++;
				}
			}
		}
		
		int max = 0;
		String str = null;
		List<String> strList = null;
		for(Entry<String, Integer> entry : stringMap.entrySet()) {
			if(entry.getValue() > max) {
				max = entry.getValue();
				str = entry.getKey();
			}
		}
		
		for(List<String> l : varStringList) {
			if(l.get(0).compareTo(str) ==  0) {
				strList = l;
			}
		}
		
		return strList;		
	}
	
	/**
	 * Generates a String-Match List, matches Strings by regex in file filename.
	 * 
	 * @param regex - String, regex to match strings in file.
	 * @param filename - String, filepath of input file.
	 * @return List<List<String>>, String-Match List generated from find operations.
	 * @throws DFAException 
	 */
	public List<List<String>> find(String regex, String filename) throws DFAException {
		List<List<String>> result = new ArrayList<List<String>>();
		
		try {
			List<ASTTree> astTreeList = TreeGenerator.makeTreeFromString(new ArrayList<String>(Arrays.asList("regex", regex)));
			NFAGenerator nfaGenerator = new NFAGenerator(astTreeList);
			NFAGraph nfaGraph = nfaGenerator.generateNFA();
			
			DFA dfa = new DFA(nfaGraph);
			TableWalker tWalker = new TableWalker(filename, dfa);
	        List<CompleteToken> findResult = tWalker.find();
	        
	        for(CompleteToken token : findResult) {
	        	result.add(token.generateList());
	        }
	        
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
		return result;
	}
	
	/**
	 * Replaces all of the Strings recognized by the regex with str in file file and puts the results in destfile.
	 * 
	 * @param regex - String, regular expression to match strings.
	 * @param str - String, to replace the matched strings with.
	 * @param filename - String, input filepath.
	 * @param destfilename - String, destination filepath.
	 * @throws DFAException 
	 */
	public void replace(String regex, String str, String filename, String destfilename) throws DFAException {
		//get find results
		List<List<String>> findResult = find(regex, filename);

    	InputStream inStream = null;
    	OutputStream outStream = null;
    	
    	try {
    		//Copy file to destination
			File file = new File(filename);
		    File destfile = new File(destfilename);
		    
		    inStream = new FileInputStream(file);
		    outStream = new FileOutputStream(destfile);
		    
		    byte[] buffer = new byte[1024];
		    int length;
    	    while ((length = inStream.read(buffer)) > 0){
    	    	outStream.write(buffer, 0, length);
    	    }
 
    	    inStream.close();
    	    outStream.close();
    	    
    	    //Get list of strings and indices.
    	   List<List<String>> replaceSet = new ArrayList<List<String>>();
    	   for (List<String> list : findResult) {
    		   for(String s : list.subList(3, list.size()-1)) {
    			   replaceSet.add(Arrays.asList(list.get(0), s));
    		   }
    	   }
    	   
    	   //check this for ordering properly.
    	   Collections.sort(replaceSet, new Comparator<List<String>>(){
    		    @Override
				public int compare(List<String> a, List<String> b) {
					// TODO Auto-generated method stub
    		    	if(Integer.valueOf(a.get(1)).compareTo(Integer.valueOf(b.get(1))) < 0) {
    		    		return 1;
    		    	}
    		    	else if(Integer.valueOf(a.get(1)).compareTo(Integer.valueOf(b.get(1))) > 0) {
    		    		return -1;
    		    	}
    		    	else {
    		    		return Integer.valueOf(a.get(1)).compareTo(Integer.valueOf(b.get(1)));
    		    	}
				}
    		});
    	    
    	   
    	   
		    StringBuilder fileContents = new StringBuilder((int)destfile.length());
		    Scanner scanner = new Scanner(destfile);
		    String lineSeparator = System.getProperty("line.separator");

		    try {
		        while(scanner.hasNextLine()) {        
		            fileContents.append(scanner.nextLine() + lineSeparator);
		        }
		    } finally {
		        scanner.close();
		    }
		    
		    StringBuffer fileString = new StringBuffer(fileContents.toString());
		    
		    for(List<String> strList : replaceSet) {
		    	fileString.replace(Integer.parseInt(strList.get(1)), Integer.parseInt(strList.get(1)) + strList.get(0).length(), str);
		    }
		    
		    scanner.close();
		    
		    BufferedWriter out = new BufferedWriter(new FileWriter(destfilename));  
	        out.write(fileString.toString());  
	        out.flush();
	        out.close(); 
		    
		    
    	}  catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
    	} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	/**
	 * Replaces all of the Strings recognized by the regex with str in file file and puts the results in destfile.
	 * This is done until there no recognized strings, or the case where the matched strings = str. This ensures that
	 * the replacement does not result in more strings that are recognized by the regex.
	 * 
	 * @param regex - String, regular expression to match strings.
	 * @param str - String, to replace the matched strings with.
	 * @param file - String, input filepath.
	 * @param destfile - String, destination filepath.
	 * @throws Exception 
	 */
	public void recursiveReplace(String regex, String str, String filename, String destfilename) throws Exception {
		
		if(str.split(regex).length > 0) {
			throw new Exception("ERROR: Regular expression and replacement string match in recursive replace call.") ;
		}
		
		//get find results
		InputStream inStream = null;
    	OutputStream outStream = null;
    	
    	try {
    		//Copy file to destination
			File file = new File(filename);
		    File destfile = new File(destfilename);
		    
		    inStream = new FileInputStream(file);
		    outStream = new FileOutputStream(destfile);
		    
		    byte[] buffer = new byte[1024];
		    int length;
    	    while ((length = inStream.read(buffer)) > 0){
    	    	outStream.write(buffer, 0, length);
    	    }
 
    	    inStream.close();
    	    outStream.close();
    	    
    		List<List<String>> findResult = find(regex, filename);
    		while(findResult.size() > 0) {
	    	   //Get list of strings and indices.
	    	   List<List<String>> replaceSet = new ArrayList<List<String>>();
	    	   for (List<String> list : findResult) {
	    		   for(String s : list.subList(3, list.size()-1)) {
	    			   replaceSet.add(Arrays.asList(list.get(0), s));
	    		   }
	    	   }
	    	   
	    	   Collections.sort(replaceSet, new Comparator<List<String>>(){
	    		    @Override
					public int compare(List<String> a, List<String> b) {
						// TODO Auto-generated method stub
	    		    	if(Integer.valueOf(a.get(1)).compareTo(Integer.valueOf(b.get(1))) < 0) {
	    		    		return 1;
	    		    	}
	    		    	else if(Integer.valueOf(a.get(1)).compareTo(Integer.valueOf(b.get(1))) > 0) {
	    		    		return -1;
	    		    	}
	    		    	else {
	    		    		return Integer.valueOf(a.get(1)).compareTo(Integer.valueOf(b.get(1)));
	    		    	}
					}
	    		});
	    	     
			   StringBuilder fileContents = new StringBuilder((int)destfile.length());
			   Scanner scanner = new Scanner(destfile);
			   String lineSeparator = System.getProperty("line.separator");

			  
				while(scanner.hasNextLine()) {        
				    fileContents.append(scanner.nextLine() + lineSeparator);
				}
				scanner.close();
				
				StringBuffer fileString = new StringBuffer(fileContents.toString());
				
				for(List<String> strList : replaceSet) {
					fileString.replace(Integer.parseInt(strList.get(1)), Integer.parseInt(strList.get(1)) + strList.get(0).length(), str);
				}
				
				scanner.close();
				
				BufferedWriter out = new BufferedWriter(new FileWriter(destfilename));  
				out.write(fileString.toString());  
				out.flush();
				out.close();
				
				findResult = find(regex, destfilename);
    		}
    	} catch(FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
    	} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	
	/**
	 * Takes in a list of strings, or expressions, evaluates them, and prints them appropriately.
	 * 
	 * @param expressions - List<String>, list of expressions tokens.
	 * @throws DFAException 
	 */
	public void print(List<String> expressions) throws DFAException {
		//Divide up continuous list of expressions into list of contained expressions
		//i.e. {{find, regex, filename},{union},{ID}}
		int i = 0;
		List<List<String>> expressionSets = new ArrayList<List<String>>();
		while(i < expressions.size()) {
			if(expressions.get(i).compareTo("find") == 0) {
				expressionSets.add(expressions.subList(i, i+3));
				i += 3;
			}
			else if(binops.contains(expressions.get(i))) {
				expressionSets.add(expressions.subList(i, i+1));
				i++;
			}
			else if(varMap.keySet().contains(expressions.get(i))) {
				expressionSets.add(expressions.subList(i, i+1));
				i++;
			}
		}
		
		//Get values of expressions
		//find or ID - > List<List<String>>
		//ID -> Int
		//bin-op -> String
		//Evaluate finds, get string match list from variables...
		List<List<List<String>>> resolvedSets = new ArrayList<List<List<String>>>();
		i=0;
		while(i < expressionSets.size()) {
			if(!binops.contains(expressionSets.get(i).get(0))) {
				if(expressionSets.get(i).get(0).compareTo("find") == 0) {
					resolvedSets.add(find(expressionSets.get(i).get(1),expressionSets.get(i).get(2)));
				}
				else if(varMap.keySet().contains(expressionSets.get(i).get(0))) {
					if(varMap.get(expressionSets.get(i).get(0)).getValueInt() != null) {
						resolvedSets.add(Arrays.asList(Arrays.asList(varMap.get(expressionSets.get(i).get(0)).getValueInt() +"")));
					}
					else {
						resolvedSets.add(varMap.get(expressionSets.get(i).get(0)).getValueStringMatchList());
					}
				}
			}
			else if(binops.contains(expressionSets.get(i).get(0))) {
				resolvedSets.add(Arrays.asList(expressionSets.get(i)));
			}
			i++;
		}		
		
		//Evaluate the expressions
		List<List<List<String>>> finalSets = new ArrayList<List<List<String>>>();
		i=0;
		List<List<String>> result = null;
		while(i < resolvedSets.size()) {
			if(binops.contains(resolvedSets.get(i).get(0).get(0)) || (i+1 < resolvedSets.size() && binops.contains(resolvedSets.get(i+1).get(0).get(0)))) {
				if(resolvedSets.get(i).get(0).get(0).compareTo("diff") == 0) {
					result = difference(resolvedSets.get(i-1), resolvedSets.get(i+1));
					resolvedSets.set(i+1, result);
				}
				else if(resolvedSets.get(i).get(0).get(0).compareTo("inters") == 0) {
					result = intersection(resolvedSets.get(i-1), resolvedSets.get(i+1));
					resolvedSets.set(i+1, result);
				}
				else if(resolvedSets.get(i).get(0).get(0).compareTo("union") == 0) {
					result = union(resolvedSets.get(i-1), resolvedSets.get(i+1));
					resolvedSets.set(i+1, result);
				}
			}
			else {
				if(result != null) {
					finalSets.add(result);
				}
				if(resolvedSets.get(i) != result) {
					finalSets.add(resolvedSets.get(i));
				}
				result = null;		
			}
			i++;
		}
		
		//Create final list of parsed strings
		List<String> printOutput = new ArrayList<String>();
		for(List<List<String>> stringListList : finalSets) {
			if(stringListList.get(0).size() == 1) {
				printOutput.add(stringListList.get(0).get(0) + "\n");
			}
			else {
				String output = "";
				for(List<String> stringList : stringListList) {
					
					int j = 0;
					int k = 0;
					while(j < stringList.size()) {
						if(stringList.get(j).compareTo("<") == 0) {
							output +=  stringList.get(j);
							k = j+1;
							j++;
							
							while(j < stringList.size()) {
								if(stringList.get(j).compareTo(">") == 0) {
									output += ">";
								}
								else if(stringList.get(j+1).compareTo(">") != 0) {
									output += stringList.get(j) + ", ";
								}
								else {
									output += stringList.get(j);
								}
								j++;
							}
						}
						else {
							output += stringList.get(j) +  " ";
						}
						j++;
					}
					output += "\n";
				}
				printOutput.add(output);
			}
		}
		
		for(String printString : printOutput) {
			System.out.println(printString);
		}
	}
	
	/**
	 * Takes in two String-Match Lists and returns the union of them.
	 * 
	 * @param list - List<List<String>>, first list.
	 * @param list2 - List<List<String>>, second list.
	 * 
	 * @return List<List<String>> result, the union of list and list2.
	 */
	public List<List<String>> union(List<List<String>> list, List<List<String>> list2) {
		HashMap<String,List<List<String>>> unionSet=new HashMap<String,List<List<String>>>();
		int flagList1=0,flagList2=0;
		//String keyStorage="";
		List<List<String>> finalResult = new ArrayList<List<String>>();
		for(List<String> temp:list){
			if(unionSet.containsKey(temp.get(0))){
				String keyStored=temp.get(0);
				List<List<String>> contained=unionSet.get(keyStored);
				List<String> copiedList=new ArrayList<String>(temp);
				List<List<String>> tempFullList=generateFullList(copiedList);
				for(List<String> tempInner:tempFullList){
					for(List<String> temp2:contained){
						if(tempInner.get(1).equals(temp2.get(1))){
							flagList1=1;
							List<String> combined=combiningLists(tempInner,temp2);
							contained.remove(temp2);
							contained.add(combined);
							unionSet.put(keyStored, contained);
							break;
						}
					}
					if(flagList1==0){
						contained.add(tempInner);
						unionSet.put(keyStored, contained);
					}
					flagList1=0;
				}
			}
			else{
				List<String> copiedList=new ArrayList<String>(temp);
				List<List<String>> tempFullList=generateFullList(copiedList);
				unionSet.put(temp.get(0), tempFullList);
			}
		}
		for(List<String> temp:list2){
			if(unionSet.containsKey(temp.get(0))){
				String keyStored=temp.get(0);
				List<List<String>> contained=unionSet.get(keyStored);
				List<String> copiedList=new ArrayList<String>(temp);
				List<List<String>> tempFullList=generateFullList(copiedList);
				for(List<String> tempInner:tempFullList){
					for(List<String> temp2:contained){
						if(tempInner.get(1).equals(temp2.get(1))){
							flagList2=1;
							List<String> combined=combiningLists(tempInner,temp2);
							contained.remove(temp2);
							contained.add(combined);
							unionSet.put(keyStored, contained);
							break;
						}
					}
					if(flagList2==0){
						contained.add(tempInner);
						unionSet.put(keyStored, contained);
					}
					flagList2=0;
				}
			}
			else{
				List<String> copiedList=new ArrayList<String>(temp);
				List<List<String>> tempFullList=generateFullList(copiedList);
				unionSet.put(temp.get(0), tempFullList);
			}
		}
		
	    Iterator<Entry<String, List<List<String>>>> itSet = unionSet.entrySet().iterator();
		while(itSet.hasNext()){
			Entry<String, List<List<String>>> entryList=itSet.next();
			List<String> tokenList=new ArrayList<String>();
			tokenList.add(entryList.getKey());
			for(List<String> inBetween:entryList.getValue()){
				for(String subsection:inBetween){
					tokenList.add(subsection);
				}
			}
			finalResult.add(tokenList);
		}
		return finalResult;
		
	}
	
	
	public List<String> combiningLists(List<String> list1, List<String> list2){
		List<String> indexesList1=list1.subList(2, list1.size()-1);
		List<String> indexesList2=list2.subList(2, list2.size()-1);
		LinkedHashSet<String> indexes=new LinkedHashSet<String>();
		for(String index:indexesList1){
			indexes.add(index);
		}
		for(String index:indexesList2){
			indexes.add(index);
		}
		List<String> combinedList=new ArrayList<String>();
		combinedList.add("<");
		combinedList.add(list1.get(1));
		combinedList.addAll(indexes);
		combinedList.add(">");
		return combinedList;
	}
	
	public List<List<String>> generateFullList(List<String> given){
		List<List<String>> tempFullList = new ArrayList<List<String>>();
		List<String> tempStorage=new ArrayList<String>();
		given.remove(0);int flag = 0;
		
		for(String sub:given){
			if(sub.equals("<")){
				flag=1;
				tempStorage.add(sub);
			}
			else if(sub.equals(">")){
				flag=0;
				tempStorage.add(sub);
				tempFullList.add(tempStorage);
			}
			else if(flag==1){
				tempStorage.add(sub);
			}
		}
		
		return tempFullList;
	}
	
	/**
	 * Takes in two String-Match Lists and returns the intersection of them.
	 * 
	 * @param list - List<List<String>>, first list.
	 * @param list2 - List<List<String>>, second list.
	 * 
	 * @return List<List<String>> result, the intersection of list and list2.
	 */
	public List<List<String>> intersection(List<List<String>> list, List<List<String>> list2) {
		List<List<String>> finalResult = new ArrayList<List<String>>();
		HashMap<String,List<List<String>>> intersectionSet=new HashMap<String,List<List<String>>>();
		HashMap<String,List<List<String>>> finalResultSet=new HashMap<String,List<List<String>>>();

		int flagList1=0;
		
		for(List<String> temp:list){
			if(intersectionSet.containsKey(temp.get(0))){
				//String keyStored=temp.get(0);
				List<List<String>> contained=intersectionSet.get(temp.get(0));
				List<String> copiedList=new ArrayList<String>(temp);
				List<List<String>> tempFullList=generateFullList(copiedList);
				for(List<String> tempInner:tempFullList){
					for(List<String> temp2:contained){
						if(tempInner.get(1).equals(temp2.get(1))){
							flagList1=1;
							List<String> combined=combiningLists(tempInner,temp2);
							contained.remove(temp2);
							contained.add(combined);
							intersectionSet.put(temp.get(0), contained);
							break;
						}
					}
					if(flagList1==0){
						contained.add(tempInner);
						intersectionSet.put(temp.get(0), contained);
					}
					flagList1=0;
				}
			}
			else{
				List<String> copiedList=new ArrayList<String>(temp);
				List<List<String>> tempFullList=generateFullList(copiedList);
				intersectionSet.put(temp.get(0), tempFullList);
			}
		}
		
		for(List<String> subList:list2){
			if(intersectionSet.containsKey(subList.get(0))){
				List<List<String>> contained=intersectionSet.get(subList.get(0));
				List<String> copiedList=new ArrayList<String>(subList);
				List<List<String>> tempFullList=generateFullList(copiedList);
				
				for(List<String> tempInner:tempFullList){
					for(List<String> temp:contained){
						
						if(tempInner.get(1).equals(temp.get(1))){
							List<String> intersectList=intersectList(tempInner,temp);
							if(intersectList!=null){
								if(finalResultSet.containsKey(subList.get(0))){
									List<List<String>> foundVal=finalResultSet.get(subList.get(0));
									foundVal.add(intersectList);
									finalResultSet.put(subList.get(0),foundVal);
								}
								else{
									List<List<String>> foundVal=new ArrayList<List<String>>();
									foundVal.add(intersectList);
									finalResultSet.put(subList.get(0),foundVal);
								}
							}
					    }
						
					}
				}

			}
		}
		
		List<String> tokenList=new ArrayList<String>();
		Entry<String, List<List<String>>> entryList;
		
		    Iterator<Entry<String, List<List<String>>>> itSet = finalResultSet.entrySet().iterator();
		    while(itSet.hasNext()){
				entryList=itSet.next();
				tokenList.add(entryList.getKey());
				for(List<String> inBetween:entryList.getValue()){
					for(String subsection:inBetween){
						tokenList.add(subsection);
					}
				}
				finalResult.add(tokenList);
				tokenList=new ArrayList<String>();
			}
		    
	    if(finalResult.isEmpty()){
			tokenList.add("");
			finalResult.add(tokenList);
		}
		return finalResult;
	}
	
	
	public List<String> intersectList(List<String> list1, List<String> list2){
		List<String> indexesList1=list1.subList(2, list1.size()-1);
		List<String> indexesList2=list2.subList(2, list1.size()-1);
		List<String> finalIndexList=new ArrayList<String>();

		LinkedHashSet<String> indexes=new LinkedHashSet<String>();
		for(String index:indexesList1){
			indexes.add(index);
		}
		for(String index:indexesList2){
			if(indexes.contains(index)){
				finalIndexList.add(index);
			}
		}
		List<String> combinedList=new ArrayList<String>();
		combinedList.add("<");
		combinedList.add(list1.get(1));
		combinedList.addAll(finalIndexList);
		combinedList.add(">");
		if(finalIndexList.isEmpty()){
			return null;
		}
		else{
			return combinedList;
		}
	}
	

	/**
	 * Takes in two String-Match Lists and returns the difference of the first minus the second.
	 * 
	 * @param list - List<List<String>>, first list to subtract from.
	 * @param list2 - List<List<String>>, second list to subtract.
	 * 
	 * @return List<List<String>> result, the difference of list and list2.
	 */
	public List<List<String>> difference(List<List<String>> list, List<List<String>> list2) {
		List<List<String>> result = new ArrayList<List<String>>();
		List<Integer> indexList =  new ArrayList<Integer>();
		
		for(List<String> stringList : list2) {
			for(List<String> stringList2 : list) {
				if(stringList2.get(0).compareTo(stringList.get(0)) == 0) {
					indexList.add(list.indexOf(stringList2));
				}
			}
		}
		
		for(List<String> stringList : list) {
			if(!indexList.contains(list.indexOf(stringList))) {
				result.add(stringList);
			}
		}
		return result;
	}

	//Getter for input
	

	public List<List<String>> getInput() {
		return input;
	}

	//Setter for input
	public void setInput(List<List<String>> input) {
		this.input = input;
	}
	
	//Getter for varMap
	
	public Map<String, Variable> getVarMap() {
		return varMap;
	}

	
	//Setter for varMap
	public void setVarMap(Map<String, Variable> varMap) {
		this.varMap = varMap;
	}
}